package 剑指offer;

public class _47礼物的最大价值 {
	/**
	 * 
	 *@time 2021年3月19日下午4:48:44
	 * 
	 *@param grid
	 *@return int
	 *
	 *@see 使用动态规划求解
	 *dp[i][j]的动态方程分四种情况：
	 *1. 	dp[i][j]=grid[0][0] 条件：i=0,j=0;
	 *2.	dp[i][j]=grid[i][j]+dp[i-1][j] 条件：i!=0 ,j=0 即在最左侧
	 *3.	dp[i][j]=grid[i][j]+dp[i][j-1] 条件： i=0,j!=0 即在第一行
	 *4.	dp[i][j]=grid[i][j]+max(dp[i-1][j],dp[i][j-1]) 条件：i！=0,j！=0   即在中间部分
	 */
	public int maxValue(int[][] grid) {
		int n = grid.length,m = grid[0].length;
		int [][]dp = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if ( i == 0 && j == 0) {
					dp[0][0] = grid[0][0];
					continue;
				}
				if (i == 0) {
					dp[i][j] = dp[i][j-1]+grid[i][j];
				}
				else if(j == 0) {
					dp[i][j] = dp[i-1][j]+grid[i][j];
				}
				else {
					if(dp[i-1][j] >= dp[i][j-1])
						dp[i][j] = grid[i][j]+dp[i-1][j];
					else
						dp[i][j] = grid[i][j]+dp[i][j-1];
				}
				
			}
		}		
		return dp[n-1][m-1];
    }
	/**
	 * 
	 *@time 2021年3月19日下午4:54:35
	 * 
	 *@param grid
	 *@return int
	 *
	 *@see跟上面的思路相似，没有而外的创建空间
	 */
	public int maxValue1(int[][] grid) {
		int n = grid.length,m = grid[0].length;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if ( i == 0 && j == 0) {
					continue;
				}
				if (i==0) {
					grid[i][j] = grid[i][j-1]+grid[i][j];
				}
				else if (j == 0) {
					grid[i][j] = grid[i-1][j]+grid[i][j];
				}
				else {
					if(grid[i-1][j] >= grid[i][j-1])
						grid[i][j] = grid[i][j]+grid[i-1][j];
					else
						grid[i][j] = grid[i][j]+grid[i][j-1];
				}
			}
		}
		return grid[n-1][m-1];
	}
	public int maxValue2(int[][] grid) {
		int n = grid.length,m = grid[0].length;
		for (int i = 1; i < n; i++) {	//初始化第一列
			grid[i][0] +=grid[i-1][0];
		}
		for (int j = 1; j < m; j++) { 	//初始化第一行
			grid[0][j] +=grid[0][j-1];
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if(grid[i-1][j] >= grid[i][j-1])
					grid[i][j] = grid[i][j]+grid[i-1][j];
				else
					grid[i][j] = grid[i][j]+grid[i][j-1];
			}
		}
		return grid[n-1][m-1];
	}
}
